This invention relates generally to digital image processing, and particularly to edge detection in digital images.
Digital images can be formed by many devices and can be used for many practical purposes. Digital image formation devices include TV cameras operating on visible or infrared light, line-scan sensors, flying spot scanners, electron microscopes, X-ray devices, such as CT scanners, and magnetic resonance imagers, for example. Practical applications of digital image formation devices include industrial automation, medical diagnosis, satellite imaging, photographic processing, surveillance, traffic monitoring, document processing, and many others.
To serve these applications, images formed by a digital image formation device are processed by a digital information processing device, such as a general purpose computer executing image processing software, to extract useful information. One very common form of digital image processing, well known in the art, is edge detection. Edge detection can be defined informally as a process for determining the location of boundaries between image regions that are of different and roughly uniform brightness. To be more precise, edge detection can be defined as a process for locating edges in an image, where an edge can be usefully defined as a point in an image where the image gradient magnitude reaches a local maximum in the image gradient direction, or equivalently, where the second derivative of brightness crosses zero in the image gradient direction. It can also be useful to define an edge as a point where the image best fits a one- or two-dimensional ideal step boundary, within a small neighborhood of the point. (Some authors define an edge to be a set of such points, and define the points themselves as edge elements. For present purposes, the distinction is unnecessary; the points will simply be called edges.)
It is recognized in the art that many local maxima of gradient magnitude (or zero-crossings in the second derivative) may exist in an image that are not the result of boundaries between regions, but rather are the result of image noise or other image artifacts. Thus, it is conventional to discard edge points whose gradient magnitude is less than some noise threshold, which threshold can be predetermined, or can be adaptively computed based on image characteristics, and which can vary from point to point in the image, or can be constant over the entire image. Other more sophisticated edge point filtering techniques are known in the art, such as the hysteresis thresholding method of Canny.
It is also recognized in the art that the existence and characteristics of a boundary between regions of different and roughly uniform brightness depends on the scale (resolution) at which the image is processed. Boundaries between small, high spatial frequency regions may not be evident in a coarse, low resolution examination of the image, while boundaries between much larger, low spatial frequency regions may not be evident in a fine, high resolution view (i.e., not seeing the forest for the trees). Thus it is known in the art to perform edge detection at a plurality of spatial frequencies or length scales as appropriate to the application.
The above definition of an edge based on gradient magnitude and direction, while precise, is based on the impractical assumption that an image can be treated as a function of two continuous variables. In practice, however, an image acquired by an image formation device as discussed above is discontinuous and quantized, consisting of an array of pixels, each pixel being disposed at an integer-valued image coordinate, and each pixel having an integer brightness values. Consequently, in practice one can only estimate gradient magnitude and gradient direction, and one can only estimate the position of a gradient maximum or a zero-crossing. Furthermore, in practice, the computational cost and speed of such an estimation must be considered, so that it is desirable to use methods of gradient estimation that are accurate, and yet at the same time computationally inexpensive and fast. However, higher accuracy gradient determination, and edge location based thereon, is typically associated with high cost and/or low speed. Also, low cost and/or high speed gradient determination, and edge location based thereon, is typically associated with low accuracy. Many estimators of gradient magnitude and direction are known in the art, which attempt to strike a reasonable balance between accuracy, computational cost, and speed.
To provide low cost and/or high speed, most known gradient estimators provide very crude estimates of gradient magnitude and direction. In this case, the gradient magnitude accuracy tends to be less for gradient directions not substantially parallel to the axes of the pixel grid, as compared with gradient magnitude accuracy for gradient directions substantially parallel to the axes of the pixel grid. Gradient direction is usually computed to only three bits of precision (i.e., approximated to one of eight discrete directions, e.g., N, NE, E, . . . ) because three-bit accuracy is relatively inexpensive; cost increases significantly beyond three bits.
Although carrying out edge detection to the nearest whole pixel using image gradients is generally straightforward and efficient, it is challenging to achieve fast, inexpensive, and accurate subpixel edge detection using image gradients. Alternatively, edge detection based on locally fitting ideal step boundaries can directly provide accurate subpixel edge positions, without requiring intermediate calculations based on an assumption of two continuous variables. Therefore, such local fitting methods dominate the art in applications requiring accurate, subpixel edge detection. However, local fitting methods are relatively expensive and/or slow, and therefore are not practical in high-accuracy applications that also require low cost and/or high speed. Consequently, there is a need for an inexpensive and/or fast method of high-accuracy subpixel edge detection.
The invention provides an apparatus and method for accurate subpixel edge detection, based on fast and inexpensive estimates of image gradient magnitude and direction. Any method of forming an image may be used, based on either image acquisition using an image formation device, or image synthesis. In either case, the image may optionally be transformed by one or more processing steps of any nature, including but not limited to optical and/or electronic image processing.
The invention provides a method and apparatus for edge detection using an array of gradient magnitude and gradient direction estimates to determine accurate subpixel positions of the edges detected.
Image gradient magnitude and direction are estimated at regularly spaced positions in the image using any gradient estimation method that provides more than three bits of gradient direction accuracy, including but not limited to the gradient estimation method described herein. In a preferred embodiment, an inexpensive gradient estimator providing around seven bits or more of magnitude and direction is used. The estimates are made at a scale (spatial resolution) appropriate to the application. The edge detection process can be performed at a plurality of scales on the same image, if appropriate. The points at which gradient is estimated at a given scale may or may not correspond to the locations of the image pixels.
In an optional step, a gradient estimate is discarded when it is determined not to correspond to a real image feature, using methods known in the art, such as discarding the gradient estimate when the magnitude of the gradient estimate falls below a noise threshold. This optional step may be performed separately, or may be combined with subsequent processing steps.
For each gradient estimate G, having magnitude G0 and direction Gxcex8, one or more neighboring estimates are chosen on each side of G, approximately along the direction Gxcex8. In a preferred embodiment, where the estimates lie on a square grid, one neighbor on either side of G is chosen, the neighbors lying along one of the compass directions N-S, E-W, NE-SW, or NW-SE, depending on which compass direction is closest in angle to Gxcex8. The magnitude of the neighbor in the direction of positive gradient is called G+, while the magnitude of the neighbor in the direction of negative gradient is called Gxe2x88x92.
The estimated gradient magnitude G0 is compared with the estimated gradient magnitudes G+ and Gxe2x88x92. of the chosen neighbors to determine whether G0 is a local maximum of gradient magnitude, also called a peak. In a preferred embodiment, G0 is a peak if G0 greater than G+ and G0xe2x89xa7 greater than Gxe2x88x92. All gradient estimates that are peaks, and that pass the optional noise thresholding step, are deemed to be edges.
It should be noted that it can also be useful, although not preferable, to consider G0 to be a peak if G0 greater than G+ and G0 greater than Gxe2x88x92. Also, for example, the gradient estimates can lie on a non-square grid, such as a hexagonal grid, there can be non-grid-unit spacing of neighbors, and neighbors can be chosen based on directions other than the eight given compass directions.
For each edge detected by the above steps, the set of gradient magnitude estimates consisting of G0 and the magnitude estimates of the above-chosen neighbors, e.g., G+ and Gxe2x88x92, form a sampled one-dimensional profile of the edge. This one-dimensional profile is approximately along the gradient direction, although the discrete nature of the grid of gradient estimates makes it impossible in general to choose neighbors exactly along the gradient direction. Furthermore, again due to the discrete nature of the grid, in some embodiments, the chosen neighbors might not lie along a straight line.
The invention provides a method and apparatus for determining subpixel edge position using a one-dimensional edge profile. In embodiments where the chosen gradient magnitude estimates along the profile are collinear, a curve-fitting method of interpolation is used to estimate the subpixel position of the gradient magnitude peak along the profile. Since there is no edge position information normal to the gradient direction, the interpolated edge position can be selected to be anywhere along a direction substantially normal to the gradient direction without significant loss of edge position information. In a preferred embodiment, for example, the interpolated edge position is selected so as to lie along a line in the gradient direction passing through G0, so that the edge position is as close to G0 as possible.
In embodiments where the chosen gradient magnitude estimates along the profile are not collinear, each estimate is first moved normal to the gradient direction so that the estimates lie along some chosen line. In a preferred embodiment, the chosen line passes through G0 in the gradient direction. Once this adjustment is made, a curve-fitting method of interpolation is used to estimate the subpixel position of the gradient magnitude peak along the adjusted profile. In a preferred embodiment, the interpolated edge position is taken to be the estimated subpixel position of the gradient magnitude peak along the adjusted profile.
In a preferred embodiment using two neighbors whose gradient magnitude estimates fare G+ and Gxe2x88x92 as described above, a parabola is fit to the points G0, G+, and Gxe2x88x92 to provide an interpolated subpixel position of a gradient peak. The maximum of the parabola, i.e., the gradient peak, is taken to be the position of the gradient magnitude peak along the profile.
In another preferred embodiment, at least one two-dimensional interpolated position of the edge can be determined along a plane position line. A plane position line is a line that is normal to the gradient direction of a gradient point associated with a local maximum of gradient magnitude, also passing through the interpolated edge position along the profile.
In a further preferred embodiment, a two-dimensional interpolated position of the edge is determined as being at the intersection point of two lines. The first line is a gradient direction line that extends along the gradient direction of the gradient point from a gradient point associated with a local maximum of gradient magnitude. The second line is the plane position line that is normal to the gradient direction, also passing through the interpolated edge position.
The accuracy of any curve fitting method depends on the extent to which the behavior of gradient magnitude in the gradient direction matches the shape of the curve in a small region that includes the chosen neighbors. Given the discrete nature of the grid, the pattern of chosen neighbors necessarily depends on gradient direction. It is recognized by the invention that curves that work well for some patterns of neighbors do not work well for others. The invention solves this problem by choosing the curve separately for each edge in accordance with gradient direction.
In a preferred embodiment, the invention uses a single interpolation curve for all gradient directions, and then adjusts the interpolation result by means of a bias function having a parameter that is a function of gradient direction. This has the effect of simulating a large variety of interpolation curve shapes by adjusting a single parameter. In a further preferred embodiment, the bias function is a power law function and the parameter is the power. In another preferred embodiment, the power law bias function is applied to a parabolic interpolation curve. In still another preferred embodiment, the apparatus includes a lookup table to determine the adjustment of the interpolation result.
The invention provides a fast, computationally inexpensive method and apparatus for edge detection that is of higher accuracy than available in the prior art, as well as providing an accurate method and apparatus for edge detection that is faster and less computationally expensive than available in the prior art.
Moreover, the invention exploits computationally inexpensive estimates of gradient magnitude and direction to achieve accurate, computationally inexpensive, and fast estimates of edge position, providing accurate edge detection in a fast and computationally inexpensive manner, even for edges that are not substantially parallel to the axes of the pixel grid.